package algorithm.poj.p1000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;
import java.util.Arrays;

/**
 * 分析：
 * 能够覆盖island的radar属于某个区间，问题就转化为：
 * 一组区间中，最少需要找多少个点，才能保证每个区间至少有一个点？
 * 
 * 这个是典型的贪心算法问题。
 * 
 * 实现：
 * 略。
 * 
 * 经验和教训：
 * 1. 之前版本的问题是MLE：可能原因是在初始化时，把输入保存在了String类型的变量lines中。以后要避免。
 * 2. 坐标直接用double就可以，不要先考虑复杂的x+sqrt(d)类型数据比较。
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P1328 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P1328.class.getResource("P1328.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

        int k = 0;
		String line = stdin.readLine();
		
        while (line != null && !"0 0".equals(line.trim())) {
        	
        	String[] tmp = line.split(" ");
	        int n = Integer.valueOf(tmp[0]);
	        int d = Integer.valueOf(tmp[1]);
	        
	        int[][] islands = new int[n][];
	        for (int i = 0; i < n; i ++) {
	        	line = stdin.readLine();
	        	tmp = line.split(" ");
	        	islands[i] = new int[2];
	        	islands[i][0] = Integer.valueOf(tmp[0]);
	        	islands[i][1] = Integer.valueOf(tmp[1]);
	        }
	        k ++;
	        System.out.println("Case " + k + ": " + minRadar(d, islands));
	        line = stdin.readLine();
	        line = stdin.readLine();
        }
	}

	private static int minRadar(int d, int[][] islands) {
		
		if (d < 0) {
			return -1;
		}
		//get all intervals
		Interval[] intervals = new Interval[islands.length];
		for (int i = 0; i < intervals.length; i ++) {
			if (islands[i][1] < 0) {
				return -1;
			}
			int dis = d*d - islands[i][1]*islands[i][1];
			if (dis < 0) {
				return -1;
			} else {
				double x = islands[i][0] - Math.sqrt(dis);
				double y = islands[i][0] + Math.sqrt(dis);
				intervals[i] = new Interval(x, y);
			}
		}
		//按照左端点从小到大的顺序排序
		Arrays.sort(intervals);
		
		//如果interval1包含interval2，那么去掉interval1
		for (int i = 0; i < intervals.length; i ++) {
			for (int j = i+1; j < intervals.length; j ++) {
				if (intervals[i].contains(intervals[j])) {
					intervals[i] = null;
					break;
				}
			}
		}
		
		//greedy
		int count = 0;
		int curIndex = -1;
		double curY = 0;
		while (true) {
			//step 1: find first interval, get its right point
			for (int i = curIndex+1; i < intervals.length; i ++) {
				if (intervals[i] != null) {
					curIndex = i;
					curY = intervals[i].y;
					intervals[i] = null;
					count ++;
					break;
				}
			}
			//step 2
			for (int i = curIndex+1; i < intervals.length; i ++) {
				if (intervals[i] != null) {
					if (intervals[i].x > curY) {
						break;
					} else if (intervals[i].y >= curY) {
						intervals[i] = null;
					}
				}
			}
			//step 3
			boolean allNull = true;
			for (int i = curIndex+1; i < intervals.length; i ++) {
				if (intervals[i] != null) {
					allNull = false;
				}
			}
			if (allNull) break;
		}
		
		return count;
	}

	
	private static class Interval implements Comparable<Interval> {
		
		private double x;
		private double y;
		
		public Interval(double x, double y) {
			this.x = x;
			this.y = y;
		}
		
		
		public boolean contains(Interval interval) {
			
			return x <= interval.x
				&& y >= interval.y;
		}

		public int compareTo(Interval interval) {
			
			return Double.compare(x, interval.x);
		}
		
		public String toString() {
			return "[" + x + ", " + y + "]";
		}
	}
}
